package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * 这道题中，给定总金额 {amount}amount 和数组 {coins}coins，要求计算金额之和等于 {amount}amount 的硬币组合数。其中，{coins}coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。
 * <p>
 * 可以通过动态规划的方法计算可能的组合数。用 {dp}[x]dp[x] 表示金额之和等于 x 的硬币组合数，目标是求 {dp}[{amount}]dp[amount]。
 * <p>
 * 动态规划的边界是 {dp}[0]=1dp[0]=1。只有当不选取任何硬币时，金额之和才为 00，因此只有 11 种硬币组合。
 * <p>
 * 对于面额为 {coin}coin 的硬币，当 {coin} <= i <= {amount} 时，如果存在一种硬币组合的金额之和等于 i - {coin}i−coin，则在该硬币组合中增加一个面额为 {
 * coin}coin 的硬币，即可得到一种金额之和等于 ii 的硬币组合。因此需要遍历 {coins}coins，对于其中的每一种面额的硬币，更新数组 {dp}dp 中的每个大于或等于该面额的元素的值。
 * <p>
 * 由此可以得到动态规划的做法：
 * <p>
 * 初始化 {dp}[0]=1dp[0]=1；
 * <p>
 * 遍历 {coins}coins，对于其中的每个元素 {coin}coin，进行如下操作：
 * <p>
 * 遍历 ii 从 {coin}coin 到 {amount}amount，将 {dp}[i - {coin}]dp[i−coin] 的值加到 {dp}[i]dp[i]。
 * 最终得到 {dp}[{amount}]dp[amount] 的值即为答案。
 * <p>
 * 上述做法不会重复计算不同的排列。因为外层循环是遍历数组 {coins}coins 的值，内层循环是遍历不同的金额之和，在计算 {dp}[i]dp[i] 的值时，可以确保金额之和等于 ii 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。
 * <p>
 * 例如，{coins}=[1,2]coins=[1,2]，对于 {dp}[3]dp[3] 的计算，一定是先遍历硬币面额 11 后遍历硬币面额 22，只会出现以下 2 种组合：
 * 3 =1+1+1
 * 3=1+2
 * <p>
 * 硬币面额 22 不可能出现在硬币面额 11 之前，即不会重复计算 3=2+13=2+1 的情况。
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 14:17<br>
 */
public class 零钱兑换II {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
